package networkCode.leetcode;


import cn.hutool.core.util.ArrayUtil;

public class LeetCode4 {

    /**
     * 4. 寻找两个正序数组的中位数
     * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
     * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
     * 你可以假设 nums1 和 nums2 不会同时为空。
     * <p>
     * 示例 1:
     * nums1 = [1, 3]
     * nums2 = [2]
     * 则中位数是 2.0
     * <p>
     * 示例 2:
     * nums1 = [1, 2]
     * nums2 = [3, 4]
     * 则中位数是 (2 + 3)/2 = 2.5
     */
    public static void main(String[] args) {
        int nums1[] = {1, 3};
        int nums2[] = {2};
        int nums3[] = null;
        String nums4[] = {"1", "2"};
        String nums5[] = {"3", "4"};

        int[] nums6 = ArrayUtil.addAll(new int[]{1, 2, 3}, new int[]{4, 5, 6});

        System.out.println(findMedianSortedArrays1(nums1, nums2));
//        System.out.println(findMedianSortedArrays(new int[]{1, 2, 3}, ));
    }

    /**
     * 官方解法
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    //i: nums1的起始位置 j: nums2的起始位置
    public static int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) return nums2[j + k - 1];//nums1为空数组
        if (j >= nums2.length) return nums1[i + k - 1];//nums2为空数组
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }

    /***
     * solution- hc
     * */
    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {

        int nums3[]=new int[nums1.length+nums2.length];
        System.arraycopy(nums1,0,nums3,0,nums1.length);
        System.arraycopy(nums2,0,nums3, nums1.length,nums2.length);
        sortArray(nums3);
        if(nums3.length%2==0){
            int temp=nums3[nums3.length/2]+nums3[nums3.length/2-1];
            return (double) temp/2;
        }
        else {
            return nums3[nums3.length/2];
        }


    }
    public static int[] sortArray(int [] array){


        //冒泡排序
        for (int i = 0; i < array.length - 1; i++) {

            for (int j = 0; j < array.length - 1 - i; j++) {

                if (array[j] > array[j + 1]) {
                    int temp = array[j];

                    array[j] = array[j + 1];

                    array[j + 1] = temp;
                }
            }
        }


        return array;
    }
}
